package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC440 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * 参考：https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order/solution/by-livorth-u-zvxp
     * 实在是个非常精妙的while循环，找规律
     * @return:
     */
    class Solution {
        public int findKthNumber(int n, int k) {
            long cur = 1;
            k--;
            while (k > 0) {
                // 以cur为根的子树节点有nodes个
                int nodes = getNodes(n, cur);
                // 如果个数比k少，那么这个部分都可以直接跳过
                if (k >= nodes) {
                    // 跳过全部
                    k = k - nodes;
                    // 往右移一位
                    cur++;
                }
                // 如果数量比k多，那么我们要找的结果就一定是以cur下的子节点
                else {
                    // 跳过当前结点
                    k = k - 1;
                    // 往下走一层
                    cur = cur * 10;
                }
            }
            return (int) cur;
        }

        // 获得以cur为根结点的子树节点数量
        private int getNodes(int n, long cur) {
            long next = cur + 1;
            long totalNodes = 0;
            while (cur <= n) {
                // 一次性求出下一层的节点个数和，要是没满就用n来减，要是满了就用next减
                totalNodes += Math.min(n - cur + 1, next - cur);
                // 进入下一层
                next = next * 10;
                cur = cur * 10;
            }
            return (int) totalNodes;
        }
    }


    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC440 an = new LC440();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
